package com.fr.lintcode;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月16日
*时间：下午6:27:24
*/
public class Q437 {
    /**
     * 贪心算法（类似哈夫曼树）
     * 错误！！！
     * @param pages: an array of integers
     * @param k: an integer
     * @return: an integer
     */
    public int copyBooks(int[] pages, int k) {
        if (pages == null || pages.length <= 0) {
            return 0;
        }
        int n = pages.length;
        List<Integer> l = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            l.add(pages[i]);
        }
        while (l.size() > k) {
            int min = Integer.MAX_VALUE;
            int start = -1;
            for (int i = 1; i < l.size(); i++) {
                int tmp = l.get(i - 1) + l.get(i);
                if (tmp < min) {
                    min = tmp;
                    start = i;
                }
            }
            l.add(start, min);
            l.remove(start - 1);
            l.remove(start);
        }
        int max = 0;
        for (int i : l) {
            if (i > max) {
                max = i;
            }
        }
        return max;
    }

    @Test
    public void testA() {
        int[] pages = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
        System.out.println(copyBooks(pages, 6));
    }
}
